package leetcode101_xqzhao

// TODO  最小路径和 【-】 动态规划

func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])

	// 动态规划 - 设置初始值
	for i := 1; i < m; i++ {
		grid[i][0] = grid[i][0] + grid[i-1][0]
	}
	for j := 1; j < n; j++ {
		grid[0][j] = grid[0][j] + grid[0][j-1]
	}
	// 动态规划 - 状态转移
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			grid[i][j] = min4(grid[i][j-1], grid[i-1][j]) + grid[i][j]
		}
	}
	return grid[m-1][n-1]
}

func min4(a int, b int) int {
	if a > b {
		return b
	}
	return a
}
